#pragma once
#include <iostream>
#include <cassert>
#include <cstdio>
using namespace std;

namespace ns_vector
{
    const int default_size = 4;

    template <class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;

        iterator begin()
        {
            return _start;
        }

        const_iterator begin() const
        {
            return _start;
        }

        iterator end()
        {
            return _end;
        }

        const_iterator end() const
        {
            return _end;
        }
    public:
        vector<T>() : _start(nullptr), _end(nullptr), _capacity(nullptr)
        {}
        
        vector<T>(size_t n, const T& val = T())
        {
            _start = new int[n];
            for(int i = 0;i < n;++i) //初始化
            {
                _start[i] = val;
            }
            _end = _start + n;
            _capacity = _end;
        }

        vector<T>(const vector<T>& v)
        {
            int capacity = v._capacity - v._start;
            int sz = v._end - v._start;
            _start = new int[capacity];
            for(int i = 0;i < sz;++i)
            {
                _start[i] = v._start[i];
            }
            _end = _start + sz;
            _capacity = _start + capacity;
        }

        void swap(vector<T>& v)
        {
            std::swap(_start, v._start);
            std::swap(_end, v._end);
            std::swap(_capacity, v._capacity);
        }

        vector<T>& operator=(vector<T> v)
        {
            swap(v);

            return *this;
        }

        void reserve(size_t n)
        {
            if(n > capacity())
            {   
                size_t sz = size();
                T* tmp = new T[n];
                if(_start)
                {
                    for(int i = 0;i < sz;++i)
                    {
                        tmp[i] = _start[i];
                    }
                    delete[] _start;
                }
                _start = tmp;
                _end = _start + sz;
                _capacity = _start + n;
            }
        }

        void push_back(const T& val)
        {
            if(_end == _capacity)
            {
                reserve(_end == nullptr ? default_size : 2 * capacity());
            }
            _start[size()] = val;
            ++_end;
        }

        iterator insert(iterator pos, const T& val)
        {
            assert(pos == nullptr || (pos >= begin() && pos < end()));
            if(_end == _capacity)
            {
                size_t n = pos - begin(); //防止迭代器失效
                reserve(_end == nullptr ? default_size : 2 * capacity());
                pos = begin() + n; 
            }
            iterator End = end();
            while(End > pos)
            {
                *End = *(End-1);
                --End;
            }
            *pos = val;
            ++_end;

            return pos;
        }

        iterator erase(iterator pos)
        {
            assert(begin() != end() && pos >= begin() && pos < end());
            iterator next = pos;
            while(next < end()-1)
            {
                *next = *(next+1);
                ++next;
            }
            --_end;

            return pos;
        }

        void pop_back()
        {
            assert(begin() != end());
            --_end;
        }

        T& operator[](size_t pos) const
        {
            assert(pos < size());
            return _start[pos];
        }

        size_t size() const
        {
            return _end - _start;
        }

        size_t capacity() const
        {
            return _capacity - _start;
        }

        bool empty()
        {
            return _start == _end;
        }

        void show()
        {
            size_t sz = size();
            for(size_t i = 0;i < sz;++i)
            {
                cout << _start[i] << " ";
            }
            cout << endl;
        }

        ~vector<T>()
        {
            if(_start)
            {
                delete[] _start;
                _start = _end = _capacity = nullptr;
            }
        }
    private:
        iterator _start;
        iterator _end;
        iterator _capacity;
    };
}